/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @ClassName   : Leetcode0350 
 * @author      : ganwei 
 * @date        : 2020年5月29日
 * @Description : Leetcode0350 两个数组的交集 II
 */
public class Leetcode0350 {
	/**
	 * -解题思路
	 */
    public int[] intersect(int[] nums1, int[] nums2) {
    	List<Integer> l = new ArrayList<Integer>();
    	boolean[] visitnums2 = new boolean[nums2.length];
    	for(int i = 0; i < nums1.length; i++){
    		for(int j = 0; j < nums2.length; j++){
    			if(nums1[i] == nums2[j] && !visitnums2[j]) {
    				l.add(nums1[i]);
    				visitnums2[j] = true;
    			}
    		}
    	}
    	int[] nums = new int[l.size()];
    	for(int i = 0; i < l.size(); i++){
    		nums[i] = l.get(i);
    	}
    	return nums;
    }
	/**
	 * -解题思路2,hashmap
	 */
    public int[] intersect_1(int[] nums1, int[] nums2) {
    	if(nums1.length > nums2.length){
    		return intersect_1(nums2,nums1);
    	}
    	
    	HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
    	
    	for(int num : nums1){
    		m.put(num, m.getOrDefault(num, 0)+1);
    	}
    	int k = 0;
    	for(int num : nums2){
    		int cnt = m.getOrDefault(num, 0);
    		if(cnt > 0){
    			nums1[k++] = num;
    			m.put(num, cnt-1);
    		}
    	}
    	return Arrays.copyOfRange(nums1, 0, k);
    }
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
